package com.hyb.algorithm.data.struct.dp;

/**
 * @author: ybhu
 * @create: 2021/08/25 08:15
 */
public class StoneGame3 {

    public static void main(String[] args) {

        //int[] piles = new int[]{5,3,4,5};
        // int[] piles = new int[]{3,9,1,2};
        int[] piles = new int[]{5, 17, 19, 1, 15, 19, 11, 9, 6, 5, 11, 7, 12, 12, 2, 14, 3, 6, 18, 3};
        StoneGame3 exec = new StoneGame3();
        System.out.println(exec.stoneGame2(piles));
    }

    public boolean stoneGame2(int[] piles) {

        int n = piles.length;

        if (n <= 0) {
            return false;
        }

        StonePair[][] dp = new StonePair[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = new StonePair(0, 0);
            }
        }

        for (int i = 0; i < n; i++) {
            dp[i][i].first = piles[i];
            dp[i][i].second = 0;
        }

        for (int left = 2; left <= n; left++) {
            for (int i = 0; i <= n - left; i++) {
                int j = left + i - 1;

                int leftPiles = piles[i] + dp[i + 1][j].second;
                int rightPiles = piles[j] + dp[i][j - 1].second;

                if (leftPiles > rightPiles) {
                    dp[i][j].first = leftPiles;
                    dp[i][j].second = dp[i + 1][j].first;
                } else {
                    dp[i][j].first = rightPiles;
                    dp[i][j].second = dp[i][j - 1].first;
                }
            }
        }


        StonePair stonePair = dp[0][n - 1];

        return (stonePair.first - stonePair.second) > 0;
    }


    /**
     * piles=[3,9,1,2]
     *
     * @param piles
     * @return
     */
    public boolean stoneGame(int[] piles) {
        int n = piles.length;

        if (n <= 0) {
            return false;
        }

        StonePair[][] dp = new StonePair[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = new StonePair();
                dp[i][j].first = 0;
                dp[i][j].second = 0;
            }
        }

        //dp[i][j] 代表的是  piles[i...j] 的中先手和后手的最大值
        //比如  dp[0,1]  就是[3,9]={9,3}  先手拿9  后手只能拿3
        for (int i = 0; i < n; i++) {
            dp[i][i].first = piles[i];
            dp[i][i].second = 0;
        }

        //斜着遍历数组
        for (int left = 2; left <= n; left++) {
            for (int i = 0; i <= n - left; i++) {
                //i 从左边开始     j 从右边开始
                int j = left + i - 1;

                // 这次先手，那么就相当于下次的后手  选piles[i]  还是 选piles[j]
                //dp[i][j].first = Math.max(piles[i] + dp[i + 1][j].second, piles[j] + dp[i][j - 1].second);

                // 下面的这两行 相当于 上面的   Math.max(piles[i] + dp[i + 1][j].second, piles[j] + dp[i][j - 1].second); 的拆分
                int leftPiles = piles[i] + dp[i + 1][j].second;


                int rightPiles = piles[j] + dp[i][j - 1].second;

                //如果 先手选择 piles[i]
                if (leftPiles > rightPiles) {
                    //如果 先手选择 piles[i]
                    dp[i][j].first = leftPiles;
                    dp[i][j].second = dp[i + 1][j].first;
                } else {
                    //如果 先手选择 piles[j]
                    dp[i][j].first = rightPiles;
                    dp[i][j].second = dp[i][j - 1].first;
                }
            }
        }

        //dp[0][n-1]  相当于 就是 选piles[ 0.... n-1]
        StonePair stonePairs = dp[0][n - 1];

        return (stonePairs.first - stonePairs.second) >= 0;
    }
}